import java.lang.System;
import java.util.HashMap;
import java.util.Map;

/**
 * 数组中出现次数超过⼀半的数字
 * 
 * 示例: 
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 */
public class MajorityElement {

    public int solution(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i] + 1));
            } else {
                map.put(nums[i], 1);
            }
        }

        int limit = nums.length >> 1;
        for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (entry.getValue() > limit) {
                return entry.getKey();
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2};
        int result = new MajorityElement().solution(nums);
        System.out.println("result: " + result);
    }
}
